package backtrackAlgorithm;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
 *@description 全排列
 *@author hkfan
 *@version 1.0
 *@create 2025/6/16 15:36
 */
public class LeetCode_46 {

    public List<List<Integer>> permute(int[] nums) {
        ArrayList<List<Integer>> lists = new ArrayList<>();
        solution(new HashSet<Integer>(),lists,new ArrayList<Integer>(),1,nums);
        return lists;
    }

    private void solution(Set<Integer> set, List<List<Integer>> lists, List<Integer> res, int index, int[] nums) {
        if (index== nums.length+1){
            lists.add(new ArrayList<>(res));
            return;
        }
        for (int num : nums) {
            if (!set.contains(num)){
                res.add(num);
                set.add(num);
                solution(set,lists,res,index+1,nums);
                set.remove(num);
                res.remove(res.size()-1);
            }
        }
    }

}
